package com.wsx.first.b;

import com.google.common.graph.ElementOrder;
import com.google.common.graph.GraphBuilder;
import com.google.common.graph.MutableGraph;

import java.util.*;

/**
 * @author: wangshunxi
 * @date: 2022/5/7 14:15
 * @Description:
 */
public class Main1192 {

    public static void main(String[] args) {
        Main1192 main1192 = new Main1192();
        main1192.criticalConnections(4, Arrays.asList(Arrays.asList(0, 1),Arrays.asList(1, 2),Arrays.asList(2, 0),Arrays.asList(1, 3)));

        MutableGraph<Integer> graph = GraphBuilder.directed().incidentEdgeOrder(ElementOrder.stable()).build();
        graph.putEdge(0, 1);
        graph.putEdge(1, 2);
        graph.putEdge(2, 0);
        graph.putEdge(1, 3);



    }
    Map<Integer,Set<Integer>> map;
    List<List<Integer>> res = new ArrayList<> ();
    Random random = new Random();
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        buildGraph(n, connections);
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        //随机取一个节点开始搜索 执行次数为首次 1 首次搜索上一个节点为-1
        //返回轮次 距离
        tarjan(random.nextInt(n), 0, -1, memo);
        return res;
    }

    private int tarjan(int node, int timestamp, int par, int[] memo) {
        memo[node] = timestamp;
        int lowTimestamp = Integer.MAX_VALUE;
        //取最短轮次
        for (int neighbor: map.get(node)) {
            //已经搜索过了
            if (neighbor == par) {
                continue;
            }
            //相邻的节点是全新的分支还没有搜索过 递归搜索相邻节点 搜索轮次加一 指定搜索的上一个节点为当前节点
            else if (memo[neighbor] == -1) {
                lowTimestamp = Math.min(lowTimestamp, tarjan(neighbor, timestamp + 1, node, memo));
            }
            //相邻的节点不是全新的分支
            else {
                lowTimestamp = Math.min(lowTimestamp, memo[neighbor]);
            }
        }
        memo[node] = Math.min(memo[node], lowTimestamp);
        if (par != -1 && lowTimestamp > memo[par]) {
            res.add(Arrays.asList(par, node));
        }
        return memo[node];
    }

    private void buildGraph(int n, List<List<Integer>> connections) {
        map = new HashMap<>();
        for (List<Integer> c: connections) {
            Set<Integer> left = map.getOrDefault(c.get(0), new HashSet<>());
            left.add(c.get(1));
            map.put(c.get(0), left);
            Set<Integer> right = map.getOrDefault(c.get(1), new HashSet<>());
            right.add(c.get(0));
            map.put(c.get(1), right);
        }
    }


}
